/**
 * @file     generateParenthesis.ts
 * @brief    [22. 括号生成](https://leetcode.cn/problems/generate-parentheses/description/)
 * @author   Zhu
 * @date     2023-03-06 23:10
 */

function generateParenthesis(n: number): string[] {
    const result = [];
    function generate(cur = '', open = 0, close = 0) {
        if (open > n || close > n) return;
        if (open < close) return;
        if (open === n && close === n) {
            result.push(cur);
            return;
        }
        generate(cur + '(', open + 1, close);
        generate(cur + ')', open, close + 1);
    }

    let cur = '(';
    generate(cur, 1, 0);
    return result;
}
